\documentclass[11pt,xcolor=dvipsnames]{beamer}

\usecolortheme[named=Blue]{structure}

\usetheme[height=7mm]{Rochester} 
\setbeamertemplate{items}[ball] 
\setbeamertemplate{blocks}[rounded][shadow=true] 

\usepackage[portuges,brazil]{babel}
\usepackage[latin1]{inputenc}
\usepackage{ae,aecompl}
\usepackage[T1]{fontenc}
\usepackage{algorithm}
\usepackage[noend]{algorithmic}
\usepackage{subfigure}
\usepackage{graphics}
\usepackage{epstopdf}
\usepackage{tikz}
\usetikzlibrary{arrows,shapes}

\usepackage{amsmath,amssymb}
\usepackage{color}
\usepackage{isorot}

\algsetup{linenosize=\scriptsize}
\algsetup{indent=18pt}

\newenvironment{changemargin}[2]{%
\begin{list}{}{%
\setlength{\topsep}{0pt}%
\setlength{\leftmargin}{#1}%
\setlength{\rightmargin}{#2}%
\setlength{\listparindent}{\parindent}%
\setlength{\itemindent}{\parindent}%
\setlength{\parsep}{\parskip}%
}%
\item[]}{\end{list}}

\setbeamercovered{dynamic}

\setbeamertemplate{items}[default]

\setbeamertemplate{navigation symbols}{}
\setbeamertemplate{footline}[page number] 

\pgfdeclarelayer{background}
\pgfsetlayers{background,main}
\tikzstyle{vertex}=[circle,fill=black!25,minimum size=20pt,inner sep=0pt]
\tikzstyle{vertex_small_red}=[circle,fill=red!15,minimum size=3pt,inner sep=0pt]
\tikzstyle{vertex_small_blue}=[circle,fill=green!24,minimum size=3pt,inner sep=0pt]
\tikzstyle{selected vertex} = [vertex, fill=red!24]
\tikzstyle{selected vertex2} = [vertex, fill=green!34]
\tikzstyle{edge} = [draw,thick,->]
\tikzstyle{weight} = [font=\small]
\tikzstyle{selected edge} = [draw,line width=5pt,-,blue!20]
\tikzstyle{ignored edge} = [draw,line width=5pt,-,black!20]


\title{Uma Aplica\c c\~ao da Metaheur\'istica Iterated Local Search \`a Solu\c c\~ao do problema de Fluxo Multiproduto Inteiro}
\institute[UFF]{Universidade Federal Fluminense, Niter\'oi-RJ\\Instituto de Computa\c c\~ao}
\author{Hugo Barbalho}
\date{setembro de 2011}


\AtBeginSection[]{\frame{\frametitle{Sum\'ario}\tableofcontents[current]}}

\begin{document}

\frame{
%\frametitle{XXLIII Simp\'osio Brasileiro de Pesquisa Operacional}
%\includegraphics<1>[width=.25\textwidth]{logoic.eps}
\titlepage}

\part{Main Part}
\frame{\frametitle{Sum\'ario}\tableofcontents[part=1]}


\section{Introdu\c c\~ao}
  
\begin{frame}  
\frametitle{Introdu\c c\~ao}

\begin{itemize}
\item Problema de Fluxo Multiproduto Inteiro (PFMI).
\end{itemize}
\begin{itemize}
\item Objetivo:
	\begin{itemize}
	\item Determinar o fluxo dos produtos pelos arcos da rede ao menor custo poss\'ivel.
	\end{itemize}
	\begin{itemize}
	\item Respeitando-se as restri\c c\~oes de conserva\c c\~ao de fluxo e de capacidade.
	\end{itemize}
\end{itemize}
\begin{itemize}
\item Estudo do trabalho:
	\begin{itemize}
	\item A aplica\c c\~ao da metaheur\'istica Iterated Local Search (ILS) ao PFMI.
	\end{itemize}
	\begin{itemize}
	\item Utilizado o m\'etodo da Descida Rand\^omica como m\'etodo para a gera\c c\~ao da solu\c c\~ao inicial utilizada pelo ILS.
	\end{itemize}
\end{itemize}
\end{frame}

\begin{frame}  
\frametitle{Introdu\c c\~ao}
\begin{itemize}
\item Aplica\c c\~ao nas \'areas de telecomunica\c c\~ao e sistemas de transporte, tais como:
	\begin{itemize}
	\item Roteamento de tr\'afego na internet.
	\end{itemize}
	\begin{itemize}
	\item Roteamento de mensagens em redes de comunica\c c\~ao.
	\end{itemize}
	\begin{itemize}
	\item Sequenciamento de opera\c c\~oes em refinarias de petr\'oleo.
	\end{itemize}
	\begin{itemize}
	\item Sequenciamento de carga.
	\end{itemize}
\end{itemize}
\begin{itemize}
\item O problema pode ser modelado por uma rede identificada por um grafo.
\end{itemize}
\begin{figure}
	\begin{tikzpicture}[scale=1.3, auto,swap]
		% First we draw the vertices
		\foreach \pos/\name in {{(0,2)/a}, {(2,0)/b}, {(2,2)/c},
		                         {(0,0)/d}}
		     \node[vertex] (\name) at \pos {$\name$};
		% Connect vertices with edges and draw weights
		\foreach \source/ \dest /\weight in {c/a/{}, c/b/{},d/a/{},d/b/{}}
		     \path[edge] (\source) -- node[weight] {$\weight$} (\dest);
		% paint the edge a--c
		%\begin{pgfonlayer}{background}
		%	\path<+->[selected edge] (a.center) -- (c.center);
		%\end{pgfonlayer}
	\end{tikzpicture}
\end{figure}
\end{frame}    

\begin{frame}  
\frametitle{Introdu\c c\~ao}
\begin{itemize}
\item Onde os produtos trafegam pelos arcos capacidados da rede a um determinado custo.
\end{itemize}
\begin{itemize}
\item O custo pode depender somente do arco ou tamb\'em estar associado aos produtos, em fun\c c\~ao dos arcos pelos quais trafegam.
\end{itemize}

\begin{figure}
	\begin{tikzpicture}[scale=1.3, auto,swap]
		% First we draw the vertices
		\foreach \pos/\name in {{(0,2)/1}, {(2,0)/2}, {(2,2)/3},
		                         {(0,0)/4},{(0,0)/5}}
		     \node[vertex] (\name) at \pos {$\name$};
		% Connect vertices with edges and draw weights
		\foreach \source/ \dest /\weight in {c/a/{(7,c1)}, c/b/{(8,c2)},d/a/{(5,c3)},d/b/{(9,c4)}}
		     \path[edge] (\source) -- node[weight] {$\weight$} (\dest);
		% paint the edge a--c
		%\begin{pgfonlayer}{background}
		%	\path<+->[selected edge] (a.center) -- (c.center);
		%\end{pgfonlayer}
	\end{tikzpicture}
\end{figure}

\end{frame}

\begin{frame}  
\frametitle{Introdu\c c\~ao}
\begin{itemize}
\item Os n\'os representam pontos de oferta e demanda dos produtos.
\end{itemize}
\begin{itemize}
\item Neste trabalho, para cada produto existe um par de n\'os origem - destino especificado.
\end{itemize}
\begin{itemize}
\item O objetivo e determinar o fluxo destes produtos na rede ao 
menor custo poss\'ivel, de forma a atender as de restri\c c\~oes:
	\begin{itemize}
	\item restri\c c\~oes de conserva\c c\~ao de fluxo;
	\end{itemize}
	\begin{itemize}
	\item restri\c c\~oes de capacidade; e
	\end{itemize}
	\begin{itemize}
	\item restri\c c\~oes de integralidade.
	\end{itemize}
\end{itemize}
\end{frame}

\section{Problema PFMI}

\begin{frame}  
\frametitle{Formula\c c\~ao Matem\'atica}
\begin{itemize}
\item Seja $G$ = ($N$,$A$) um grafo orientado representando uma rede com p produtos, $a$ arcos e $n$ n\'os,
sendo as cardinalidades dos conjuntos $N$ e $A$ iguais a $n$ e $a$, respectivamente.
\end{itemize}
\begin{itemize}
\item A formula\c c\~ao matem\'atica do problema \'e posta da seguinte maneira:
\end{itemize}
\begin{center}
	\begin{equation}
		min\,z\,=\,cx 
	\end{equation}
	\begin{equation}
		suj.a\,\,Nx^{i}=b^{i}, \,\,i=1,..,p
	\end{equation}
	\begin{equation}
		I.x \leq u 
	\end{equation}
	\begin{equation}
		x \in Z_{+}
	\end{equation}
\end{center}
\end{frame}

\begin{frame}  
\frametitle{Representa\c c\~ao}
\begin{figure}
	\begin{tikzpicture}[scale=1, auto,swap]
		% First we draw the vertices
		\foreach \pos/\name in {{(5,4)/3},
		                         {(4,7)/4},{(2,6)/5}}
		     \node[vertex] (\name) at \pos {$\name$};

		\node[selected vertex2] (2) at (3,2) {$2$};
		\node[selected vertex] (1) at (0,4) {$1$};

		\foreach \pos/\name in {{(4,7.7)/A},{(4.5,7.7)/A},{(4.25,8)/A}}
		     \node[vertex_small_red] (\name) at \pos {$\name$};
		\foreach \pos/\name in {{(5.7,4)/B},{(6,4)/B},{(5.7,4.4)/B},{(6,4.4)/B}}
		     \node[vertex_small_blue] (\name) at \pos {$\name$};
		% Connect vertices with edges and draw weights
		\foreach \source/ \dest /\weight in {1/2/{1}, 2/3/{2},3/4/{4},4/5/{5},5/1/{7},5/2/{6},3/1/{3}}
		     \path[edge] (\source) -- node[weight] {$\weight$} (\dest);
		% paint the edge a--c
		%\begin{pgfonlayer}{background}
		%	\path<+->[selected edge] (a.center) -- (c.center);
		%\end{pgfonlayer}
	\end{tikzpicture}
\end{figure}
\end{frame}

\begin{frame}  
\frametitle{Fim}
\[ N =  \left( \begin{array}{ccccccc}
1 & 0 & -1 & 0 & 0 & 0 & -1\\
-1 & 1 & 0 & 0 & 0 & -1 & 0 \\
0 & -1 & 1 & 1 & 0 & 0 & 0\\
0 & 0 & 0 & -1 & 1 & -1 & 0\\
0 & 0 & 0 & 0 & -1 & 1 & 1 \end{array} \right)\] 

Obrigado!
\end{frame}

\end{document}
